package com.algorithm.liyc.echa;

import com.algorithm.liyc.entity.TreeNode;
import javafx.scene.chart.ValueAxis;

/**
 * 0701.二叉搜索树中的插入操作
 *
 * 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。
 * 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
 *
 * 提示：
 * ● 给定的树上的节点数介于 0 和 10^4 之间
 * ● 每个节点都有一个唯一整数值，取值范围从 0 到 10^8
 * ● -10^8 <= val <= 10^8
 * ● 新值和原始二叉搜索树中的任意节点值都不同
 *
 * 只要遍历二叉搜索树，找到空节点 插入元素就可以了，那么这道题其实就简单了。
 * @author Liyc
 * @date 2024/1/15 17:29
 **/

public class Solution23 {
    /**
     * 递归法
     * @param root
     * @param val
     * @return
     */
    public TreeNode insertIntoBST1(TreeNode root, int val) {
        if (root == null) {
            TreeNode node = new TreeNode(val);
            return node;
        }
        if (root.val > val) {
            root = insertIntoBST1(root.left, val);
        }
        if (root.val < val) {
            root = insertIntoBST1(root.right, val);
        }
        return root;
    }

    /**
     * 迭代法
     * @param root
     * @param val
     * @return
     */
    public TreeNode insertIntoBST2(TreeNode root, int val) {
        if (root == null) {
            TreeNode node = new TreeNode(val);
            return node;
        }
        TreeNode cur = root;
        TreeNode pre = root;
        while (cur != null) {
            pre = cur;
            if (cur.val > val) {
                cur = cur.left;
            }
            if (cur.val < val) {
                cur = cur.right;
            }
        }
        if (pre.val > val) {
            pre.left = new TreeNode(val);
        }
        if (pre.val < val) {
            pre.right = new TreeNode(val);
        }
        return root;
    }
}
